#include <stdio.h>
#include <stdlib.h>
#include <cmath>
#include <algorithm>
#include <queue>
#include "binary_tree.h"

struct node
{
    int element;
    binary_tree left_son;
    binary_tree right_son;
};


int getElment(position p)
{
    if (p == NULL)
    {
        return -1;
    }

    return p->element;
}

position getLeftson(position p)
{
    if (p == NULL)
    {
        return NULL;
    }

    return p->left_son;

}
position getRightson(position p)
{
    if (p == NULL)
    {
        return NULL;
    }

    return p->right_son;

}

binary_tree create(int length, int* elements)
{
    if(length <= 0)
        return NULL;
    position p, new_node;
    binary_tree b_t;
    int i = 0;

    // the first node
    p = (position)malloc(sizeof(node));
    p -> element = elements[0];
    p -> left_son = NULL;
    p -> right_son = NULL;
    b_t = p;

    for(i = 1; i < length; i++ )
    {
        printf("%d\n", i);
        new_node = find(elements[i], b_t);

        if(new_node -> element != elements[i])
        {
            p = (position)malloc(sizeof(node));
            p -> element = elements[i];
            p -> left_son = NULL;
            p -> right_son = NULL;
            if(elements[i] < new_node->element)
                new_node->left_son = p;
            else 
                new_node->right_son = p;
            
        }
    }
    return b_t;

}


position find(int need_element, binary_tree b_t)
{
    if (b_t == NULL)
        return NULL;

    position p = b_t;

    while(1)
    {
        if((need_element < p->element) && (p->left_son != NULL))
        {
            p = p->left_son;
        } 
        else if((need_element > p->element) && (p->right_son != NULL))
        {
            p = p->right_son;
        }   
        else
        {
            break;
        }
    }
    return p;
}


position findbyrecursion(int need_element, binary_tree b_t)
{
    if(b_t == NULL)
        return NULL;
    if (b_t->element > need_element)
    {
        return findbyrecursion(need_element, b_t->left_son);
    }
    else if (b_t->element < need_element)
    {
        return findbyrecursion(need_element, b_t->left_son);
    }
    return b_t;
}

void print(binary_tree b_t)
{
    printf("print function call\n");
    if(b_t == NULL)
        return;

    position p = b_t;
    if(p->left_son != NULL)
    {
        printf("left_son\n");
        print(p->left_son);
    }
    printf("myself\n");    
    printf("%d\n", p->element);

    if(p->right_son != NULL)
    {
        printf("right_son\n");
        print(p->right_son);
    }
        
}

void delete_tree(binary_tree b_t)
{
    if(b_t == NULL)
        return;
    delete_tree(b_t -> left_son);
    delete_tree(b_t -> right_son);
    delete(b_t);
    return;
}

int getNodeNum(binary_tree b_t)
{
    if(b_t == NULL)
        return 0;
    return(getNodeNum(b_t->left_son) + getNodeNum(b_t->right_son) + 1);
}

int Depth(binary_tree b_t)
{
    if(b_t->left_son == NULL && b_t->right_son == NULL)
        return 0;
    if(b_t -> left_son == NULL)
        return Depth(b_t->right_son) + 1;
    if (b_t -> right_son == NULL)
    {
        return Depth(b_t->left_son) + 1;
    }
    return(std::max(Depth(b_t->left_son), Depth(b_t->right_son)) + 1);
}

void levelPrint(binary_tree b_t)
{
    if(b_t == NULL)
    {
        printf("This binary_tree is empty\n");
        return;
    }
    int depth = 0;
    int leftspacelength = 0;
    int rightspacelength = 0;
    position p;
    std::queue<binary_tree> q;
    depth = Depth(b_t);
    q.push(b_t);
    leftspacelength = depth - 1;
    rightspacelength = depth + 1;
    while( !q.empty())
    {   
        p = q.front();
        q.pop();
        printf("%d\n", p->element);
        if(p->left_son != NULL)
        {
            q.push(p->left_son);
        }
        if (p->right_son != NULL)
        {
            q.push(p->right_son);
        }
    }
}
//position head as the input parameter can't change the value of the head but *head.
void Convert2list(binary_tree b_t, position &head, position &tail)
{
    if (b_t == NULL)
    {

        head = NULL;
        tail = NULL;
    }

    else if (b_t->left_son == NULL && b_t->right_son == NULL)
    {
        printf("1  call Convert2list %d\n", b_t->element);
        head = b_t;
        tail = b_t;
        printf("head %d tail %d\n", head->element, tail->element);
    }
    else if (b_t->left_son == NULL)
    {
        printf("2  call Convert2list %d\n", b_t->element);

        head = b_t;
        Convert2list(b_t->right_son, b_t->right_son, tail);
        b_t->right_son->left_son = b_t;
        printf("head %d tail %d\n", head->element, tail->element);
    }
    else if (b_t->right_son == NULL)
    {
        
        printf("3  call Convert2list %d\n", b_t->element);

        tail = b_t;
        Convert2list(b_t->left_son, head, b_t->left_son);
        b_t->left_son->right_son = b_t;
        printf("head %d tail %d\n", head->element, tail->element);
    }
    else
    {
        printf("4  call Convert2list %d\n", b_t->element);
    
        Convert2list(b_t->left_son, head, b_t->left_son);
        Convert2list(b_t->right_son, b_t->right_son, tail);
        b_t->right_son->left_son = b_t;
        b_t->left_son->right_son = b_t;
        printf("head %d tail %d\n", head->element, tail->element);
    }

    
    printf("%d\n", b_t->element);
    position p;
    p = head;
    while( p != NULL)
    {
        printf("head print %d\n", getElment(p));
        p = getRightson(p);
    }

    p = tail;
    while( p != NULL)
    {
        printf("tail print %d\n", getElment(p));
        p = getLeftson(p);
    }
    printf("\n\n");
}

int getNodeNum4n(binary_tree b_t, int level)
{
    if (b_t == NULL || level > Depth(b_t))
    {
        return 0;
    }

    if(level == 0)
    {
        printf("level is 0\n");
        return 1;
    }

    return getNodeNum4n(b_t->right_son, level-1) + getNodeNum4n(b_t->left_son, level-1);
}

int gettreeleveas(binary_tree b_t)
{
    if (b_t == NULL)
    {
        printf("b_t is NULL\n");
        return 0;
    }

    if (b_t->left_son==NULL && b_t->right_son==NULL)
    {
        printf("I'm a left\n");
        return 1;
    }

    return gettreeleveas(b_t->left_son) + gettreeleveas(b_t->right_son);
}

int getFullNodes(binary_tree b_t)
{
    if (b_t == NULL)
    {
        printf("b_t is NULL\n");
        return 0;
    }

    if (b_t->left_son != NULL && b_t->right_son != NULL)
    {
        return getFullNodes(b_t->left_son) + getFullNodes(b_t->right_son) + 1;
    }

    return getFullNodes(b_t->left_son) + getFullNodes(b_t->right_son);
}